package spelling;

import java.util.List;
import java.util.Set;

import sun.security.krb5.internal.crypto.crc32;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;

/** 
 * An trie data structure that implements the Dictionary and the AutoComplete ADT
 * @author You
 *
 */
public class AutoCompleteDictionaryTrie implements  Dictionary, AutoComplete {

    private TrieNode root;
    private int size;
    

    public AutoCompleteDictionaryTrie()
	{
		root = new TrieNode();
	}
	
	
	/** Insert a word into the trie.
	 * For the basic part of the assignment (part 2), you should ignore the word's case.
	 * That is, you should convert the string to all lower case as you insert it. */
	public boolean addWord(String word)
	{
	    //TODO: Implement this method.
		word = word.toLowerCase();
		if (isWord(word)) {
			return false;
		}
		
		
		char[] charArray = word.toCharArray();
		TrieNode curr = root;
		for (int i = 0; i < charArray.length; i++) {
			char c = charArray[i];
			
			if (curr.getChild(c) == null) {
				curr = curr.insert(c);				
			}
			else {
				curr = curr.getChild(c);
			}
			
			if (curr.getText().equals(word)) {
				curr.setEndsWord(true);
				break;
			}
		}
		
		this.size ++;
	    return true;
	}
	
	/** 
	 * Return the number of words in the dictionary.  This is NOT necessarily the same
	 * as the number of TrieNodes in the trie.
	 */
	public int size()
	{
	    //TODO: Implement this method
	    return this.size;
	}
	
	
	/** Returns whether the string is a word in the trie */
	@Override
	public boolean isWord(String s) 
	{	
		if (geTrieNodeByWord(s)==null) {
			return false;
		}else {
			return true;
		}
	}
	
	
	
	
	private TrieNode geTrieNodeByInnerText(String text, Boolean isWord) {
		text = text.toLowerCase();
	    // TODO: Implement this method
		if (text.isEmpty() || this.size == 0) {
			return null;
		}
		
		TrieNode found = null;
		char[] charArray = text.toCharArray();
		TrieNode curr = root;
		for (int i = 0; i < charArray.length; i++) {
			char c = charArray[i];			
			if (curr.getChild(c) == null) {
				break;
			}
			else {
				curr = curr.getChild(c);
				if (curr.getText().equals(text)) {
					if (isWord) {
						if (curr.endsWord()) {
							found = curr;
							break;
						}
					}else {
						found = curr;
						break;
					}
				}
			}
		}		
		
		return found;
	}
		
	/**
	 * 
	 * @param word the word you want to get
	 * @return TrieNode returned
	 */
	private TrieNode geTrieNodeByWord(String word) {
		return geTrieNodeByInnerText(word, true);
	}
	
	
	private TrieNode geTrieNodeByStem(String word) {
		return geTrieNodeByInnerText(word, false);
	}
	

	/** 
	 *  * Returns up to the n "best" predictions, including the word itself,
     * in terms of length
     * If this string is not in the trie, it returns null.
     * @param text The text to use at the word stem
     * @param n The maximum number of predictions desired.
     * @return A list containing the up to n best predictions
     */@Override
     public List<String> predictCompletions(String prefix, int numCompletions) 
     {
    	 // TODO: Implement this method
    	 // This method should implement the following algorithm:
    	 // 1. Find the stem in the trie.  If the stem does not appear in the trie, return an
    	 //    empty list
    	 // 2. Once the stem is found, perform a breadth first search to generate completions
    	 //    using the following algorithm:
    	 //    Create a queue (LinkedList) and add the node that completes the stem to the back
    	 //       of the list.
    	 //    Create a list of completions to return (initially empty)
    	 //    While the queue is not empty and you don't have enough completions:
    	 //       remove the first Node from the queue
    	 //       If it is a word, add it to the completions list
    	 //       Add all of its child nodes to the back of the queue
    	 // Return the list of completions
    	 List<String> completions = new ArrayList<>();
    	 if (numCompletions ==0) {
			return completions;
		}
    	 
    	
    	TrieNode stemNode = geTrieNodeByStem(prefix);
    	
    	if (prefix.isEmpty()) {
			stemNode = root;
		}
    	
    	if (stemNode != null) {
			LinkedList<TrieNode> queue = new LinkedList<>();
			queue.add(stemNode);
			while (!queue.isEmpty()) {
				TrieNode node = queue.poll();
				if (node.endsWord()) {
					completions.add(node.getText());
					if (completions.size() == numCompletions) {
						break;
					}
				}
				for(Character c : node.getValidNextCharacters()){
					queue.add(node.getChild(c));
				}
			}
			
		}
    	 
        return completions;
     }

 	// For debugging
 	public void printTree()
 	{
 		printNode(root);
 	}
 	
 	/** Do a pre-order traversal from this node down */
 	public void printNode(TrieNode curr)
 	{
 		if (curr == null) 
 			return;
 		
 		System.out.println(curr.getText());
 		
 		TrieNode next = null;
 		for (Character c : curr.getValidNextCharacters()) {
 			next = curr.getChild(c);
 			printNode(next);
 		}
 	}
 	

	
}